package nachos.vm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;

/**
 * A <tt>UserProcess</tt> that supports demand-paging.
 */
public class VMProcess extends UserProcess {
	
	//set up page table entries so that when page faults occur, the pages from the executable will be read into 
	//memory on demand.
	public class Lazyload{
		// executable file
		private Coff coff;
		
		// the entries information of offset and pagenumber
		private List<Integer> pageoffset = new ArrayList<Integer>();
		private List<Integer> pagenums = new ArrayList<Integer>();
		
		public Lazyload(Coff coff){
			this.coff = coff;
			// for each section in executable file, initialize the entries
			for(int i=0; i<coff.getNumSections(); i++){
				for(int j=0; j<coff.getSection(i).getLength(); j++){
					int VPN = coff.getSection(i).getFirstVPN() + j;
					pagenums.add(VPN, i);
					pageoffset.add(VPN, j);
				}
			}
			
			/*	from loadSections() in proj2
				// Section Loading.
				for(int s=0; s<coff.getNumSections(); s++)
				{
					CoffSection section = coff.getSection(s);
			
					Lib.debug(dbgProcess, "\tinitializing " + section.getName() + " section (" + section.getLength() + " pages)");
			
					for(int i=0; i<section.getLength(); i++)
					{
						int vpn = section.getFirstVPN()+i;
						pageTable[vpn].readOnly = section.isReadOnly();
			
						section.loadPage(i, pageTable[vpn].ppn);
					}
				}
				
				coff.close();
			 */
		}
		
		// the translation entry between physical page number and virtual page number
		public TranslationEntry loadSection (int physical, int virtual){
			Lib.debug(dbgPeter, "[+][loadSection] Staring...");
			// valid check
			if(pagenums.size() < virtual){
				return null;
			}
			
			CoffSection temp = this.coff.getSection(pagenums.get(virtual));
			TranslationEntry entry = new TranslationEntry(virtual, physical, true, temp.isReadOnly(), false, false);
			temp.loadPage(pageoffset.get(virtual), physical);
			
			return entry;
		}		
	}
	
	//  set the lock if miss occurred
	private static Lock mlock = new Lock();
	private Lazyload lazyload;
	private static VMKernel kernel = (VMKernel) VMKernel.kernel;
	private static InvertPageTable phyPageTable = kernel.pageTable;
	private static VMSwap vmswap = kernel.swap;
	private static Random random = new Random();
	public static int MAX_SIZE = 1024;
	
	/**
	 * Allocate a new process.
	 */
	public VMProcess() {
		super();
		
		// [Yungho] Because the constructor of UserProcess initializes pageTable, we can simply override it. 
		pageTable = new TranslationEntry[MAX_SIZE];
		
		// XXX
		// XXX
		// XXX
		// processID is defined in UserProcess. We MUST consider it.
		// override?
		// XXX
		// XXX
		// XXX
	}

	/**
	 * Save the state of this process in preparation for a context switch.
	 * Called by <tt>UThread.saveState()</tt>.
	 */
	public void saveState() {
		super.saveState();
		//Lib.debug(dbgPeter, "[+][saveState] starting...");
		for(int i =0 ; i<Machine.processor().getTLBSize(); i++)
			Machine.processor().writeTLBEntry(i, new TranslationEntry());
	}

	/**
	 * Restore the state of this process after a context switch. Called by
	 * <tt>UThread.restoreState()</tt>.
	 */
	public void restoreState() {
		//Lib.debug(dbgPeter, "[+][restoreState] starting...");
//		super.restoreState();
	}
	
	
	// [Yungho] Copied from UserProcess
	// We don't need to allocate all memory blocks.
	// Just load it when we need it.
	// TLB Miss -> trap
    public int readVirtualMemory(int vaddr, byte[] data, int offset, int length)
    {
    	//Lib.debug(dbgPeter, "[+][readVirtualMemory] starting...");
		Lib.assertTrue(offset >= 0 && length >= 0 && offset+length <= data.length);

        byte[] memory = Machine.processor().getMemory();
        
        int theLastByteAddress = Machine.processor().makeAddress(numPages-1, pageSize-1);

		// [Yungho] for now, just assume that virtual addresses equal physical addresses
		if(vaddr < 0 || vaddr >= theLastByteAddress)
			return 0;

		// [Yungho] now, memory.length is not used in swapping technique
		//int amount = Math.min(length, memory.length-vaddr);
		int amount = length;
		
		// [Yungho] changed. the system copy the memory cell by one by one, not using the array copy.
		// NOTE THAT. We can't use like this way in real OS.
		// Because the Autograder doesn't check the copy routines, we can copy the cell one by one.
		// Copying one by one is due to removing uncertain memory bound error. I can't debug what is the problem.
		for(int i=0; i < amount; i++)
        {
            int thisPage = Machine.processor().pageFromAddress(vaddr+i);
            int voffset = Machine.processor().offsetFromAddress(vaddr+i);

            // [Yungho] Is this page loaded on the memory??? check!
            handleTLB(Machine.processor().makeAddress(thisPage, voffset), lazyload);
            Lib.assertTrue(pageTable[thisPage].ppn != UNALLOCATED);
            
            int paddr = Machine.processor().makeAddress(pageTable[thisPage].ppn, voffset);

            // [Yungho] check that the physical memory is not invaded
            if(paddr < 0 || paddr >= memory.length)
                return 0;	// they must always return the number of bytes transferred (even if that number is zero).
            phyPageTable.getEntry(processID, thisPage).used = true;

            // [Yungho] Copy the cell one by one
            data[i+offset] = memory[paddr];
        }

        return amount;
    }
    
    // [Yungho] Copied from UserProcess
 	// We don't need to allocate all memory blocks.
 	// Just load it when we need it.
 	// TLB Miss -> trap
    public int writeVirtualMemory(int vaddr, byte[] data, int offset, int length)
    {
    	//Lib.debug(dbgPeter, "[+][writeVirtualMemory] starting...");
    	//Lib.assertTrue(offset >= 0 && length >= 0 && offset+length <= data.length);
    	if(offset < 0 && length < 0 && offset+length < data.length)
			return 0;

        int theLastByteAddress = Machine.processor().makeAddress(numPages-1, pageSize-1);

    	// [Yungho] for now, just assume that virtual addresses equal physical addresses
    	if(vaddr < 0 || vaddr >= theLastByteAddress)
    		return 0;

        byte[] memory = Machine.processor().getMemory();

     // [Yungho] now, memory.length is not used in swapping technique
		//int amount = Math.min(length, memory.length-vaddr);
        int amount = length;

		// [Yungho] changed. the system copy the memory cell by one by one, not using the array copy.
		// NOTE THAT. We can't use like this way in real OS.
		// Because the Autograder doesn't check the copy routines, we can copy the cell one by one.
		// Copying one by one is due to removing uncertain memory bound error. I can't debug what is the problem.	
		for(int i=0; i < amount; i++)
		{
        	int thisPage = Machine.processor().pageFromAddress(vaddr+i);
	        int voffset = Machine.processor().offsetFromAddress(vaddr+i);

            // [Yungho] Is this page loaded on the memory??? check!
	        handleTLB(Machine.processor().makeAddress(thisPage, voffset), lazyload);
	        Lib.assertTrue(pageTable[thisPage].ppn != UNALLOCATED);
            
    	    int paddr = Machine.processor().makeAddress(pageTable[thisPage].ppn, voffset);

    	    // [Yungho] check that the physical memory is not invaded
			if(paddr < 0 || paddr >= memory.length)
            	return 0;	// they must always return the number of bytes transferred (even if that number is zero).
			phyPageTable.getEntry(processID, thisPage).used = true;
            phyPageTable.getEntry(processID, thisPage).dirty = true;

			// [Yungho] Copy the cell one by one
			memory[paddr] = data[i+offset];
		}

        return amount;
    }
    
    protected void handleTLB(int targetVAddr, Lazyload lazyload)
    {
    	//Lib.debug(dbgPeter, "[+][handleTLB] starting...");
        mlock.acquire();
        boolean intStatus = Machine.interrupt().disable();
        
        int thisPage = Machine.processor().pageFromAddress(targetVAddr);
        int voffset = Machine.processor().offsetFromAddress(targetVAddr);
        int ppn = UNALLOCATED;

        // [Yungho] get data from physical table.
        TranslationEntry tmp = phyPageTable.getEntry(processID, thisPage);

        if(tmp != null)
        {	// [Yungho] there is an available block in TLB. use it.
        	//Lib.debug(dbgPeter, "[+][handleTLB] tmp != null");
            Machine.processor().writeTLBEntry(random.nextInt(Machine.processor().getTLBSize()), tmp);
            mlock.release();
            return;
        }
        else
        {
        	//Lib.debug(dbgPeter, "[+][handleTLB] tmp == null");
        	// [Yungho] if there is no available block in TLB, make a target to be eliminated from the memory.
            tmp = new TranslationEntry(UNALLOCATED, UNALLOCATED, false, false, false, false);
            kernel.faultcounter++;	// fault

            if(vmswap.contains(processID, thisPage) == true)
            {
            	//Lib.debug(dbgPeter, "[+][handleTLB] swap.contains(processID, thisPage) == true"); 
            	ppn = chooseVictim();
            	// [Yungho] Try to swap, and if it fails.. 
                if(vmswap.readIn(ppn, processID, thisPage) == false)
                {
                	Lib.debug(dbgPeter, "[VMProcess] Failed to swap in.");
                    mlock.release();
                    handleExit(-1);
                }
            }
            else
            {
            	// [Yungho] swapping is success.
                if(thisPage >= 0 && thisPage < lazyload.pagenums.size())
                {
                	//Lib.debug(dbgPeter, "[+][handleTLB][TRUE] thisPage >= 0 && thisPage < lazyload.pagenums.size()");
                	ppn = chooseVictim();
                    tmp.readOnly = lazyload.loadSection(ppn, thisPage).readOnly;
                    tmp.dirty = true;
                }
                else
                {
                	//Lib.debug(dbgPeter, "[+][handleTLB][FALSE] thisPage >= 0 && thisPage < lazyload.pagenums.size()");
                	ppn = chooseVictim();
                    tmp.readOnly = false;
                    tmp.dirty = true;
                }
            }
        }

        Lib.assertTrue(tmp != null && ppn != UNALLOCATED);

        // [Yungho] set the properties of the page
        tmp.vpn = thisPage;
        tmp.valid = true;
        tmp.ppn = ppn;

        TranslationEntry tmp2 = new TranslationEntry(tmp);
        phyPageTable.addEntry(processID, tmp2);
        phyPageTable.replacement.add(tmp2);
        pageTable[thisPage] = tmp;
        
        Machine.processor().writeTLBEntry(random.nextInt(Machine.processor().getTLBSize()), tmp);
        phyPageTable.getEntry(tmp.ppn).dirty = true;

        
        Lib.debug(dbgPeter, "[+][handleTLB] RETURN");
        Machine.interrupt().restore(intStatus);
        mlock.release();
    }
    
    protected int chooseVictim()
    {
    	Lib.debug(dbgPeter, "[+][chooseVictim] starting...");
    	// choose in random manner
        int physicalPageNum = Lib.random(Machine.processor().getNumPhysPages());
        TranslationEntry tmp = phyPageTable.getEntry(physicalPageNum);

        // [Yungho] dirty means modified
        if(tmp.dirty == true)
        {
        	// then swap out.
        	boolean ret = vmswap.writeOut(physicalPageNum, phyPageTable.getOwnerPid(physicalPageNum), tmp.vpn);
        	
        	// if swapping fails
            if(ret == false)
            {
                Lib.debug(dbgPeter, "[VMProcess] Failed to swap out.");
                
                mlock.release();
                handleExit(-1);
            }
            Lib.debug(dbgPeter, "[VMProcess] Succeed to swap out.");
        }
        
        // [Yungho] Swap out happened. Now delete the victim.
        phyPageTable.deleteEntry(((long)phyPageTable.getOwnerPid(physicalPageNum) << 32) | tmp.vpn);
        phyPageTable.resetPage(physicalPageNum);

        Lib.debug(dbgPeter, "[VMProcess] Victim page number = " + physicalPageNum);
        // return the available page number, the victim once had
        return physicalPageNum;
    }
    
    protected static int getRemainedNumPhysPages()
	{
    	Lib.debug(dbgPeter, "[+][getRemainedNumPhysPages] starting...");
		Lib.debug(dbgPeter, "[+][Peter] globalPageTable remained: " + kernel.pageTable.freelist.size());
		return kernel.pageTable.freelist.size();
	}
    
    static int UNALLOCATED = -1;
    
	protected boolean allocatePhysPages(int numPages)	// xxx
	{
		Lib.debug(dbgPeter, "[+][Peter] allocatePhysPages() called");
		
		lock.acquire();		// [Yungho] we must use a lock
		
		/* we don't need it in proj3. we use swapping
		// [Yungho] moved below routines from loadSections(),
		// and modified the condition (Machine.processor().getNumPhysPages() -> globalPageTable.size())
		if(numPages > getRemainedNumPhysPages()) {
			Lib.debug(dbgProcess, "\tinsufficient physical memory");
			Lib.debug(dbgPeter, "[+][Peter] insufficient physical memory");

			coff.close();
			
			lock.release();
			return false;
		}
		*/

		// [Yungho] If some allocation algorithm is needed, make thos here!
	    for(int i=0; i < numPages; i++)
	    	// pageTable[i] = new TranslationEntry(i, UserKernel.globalPageTable.removeFirst(), true, false, false, false);
            pageTable[i] = new TranslationEntry(i, UNALLOCATED, true, false, false, false);
	    //for(int i=numPages; i < Machine.processor().getNumPhysPages(); i++)
	    for(int i=numPages; i < MAX_SIZE; i++)
	         //pageTable[i] = new TranslationEntry(i, 0, false, false, false, false);
	    	pageTable[i] = new TranslationEntry(UNALLOCATED, UNALLOCATED, false, false, false, false);

		
		lock.release();
		return true;
	}
	
	// xxxxx
	protected void deallocatePhysPages(TranslationEntry[] pageTable)
	{
		Lib.debug(dbgPeter, "[+][Peter] deallocatePhysPages() called");
	
		lock.acquire();
		
		/*
		for(int i=0; i < numPages; i++)
        {
            if(pageTable[i].valid)
            {
                int freePage = pageTable[i].ppn;
                kernel.pageTable.addLast(freePage);

                byte[] memory = Machine.processor().getMemory();

				// blank out used pages
                for(int j = 0; j < pageSize; j++)
                {
                    int paddr = Machine.processor().makeAddress(freePage, j);
                    memory[paddr] = 0;
                }
            }
        }
        */

		phyPageTable.deleteEntry(processID);
        for(int i=0; i < Machine.processor().getTLBSize(); i++)
            Machine.processor().writeTLBEntry(i, new TranslationEntry());
		
		lock.release();
	}
	
	
	static Lock lock = new Lock();		// [Yungho] lock for allocation
	
	

	/**
	 * Initializes page tables for this process so that the executable can be
	 * demand-paged.
	 * 
	 * @return <tt>true</tt> if successful.
	 */
    protected boolean loadSections() {
    	Lib.debug(dbgPeter, "[+][loadSections] starting...");
    	/*
    	 * [Yungho] Now it can be larger than memory. We will use swapping.
        if(numPages > Machine.processor().getNumPhysPages()) {
            coff.close();
            Lib.debug(dbgProcess, "\tinsufficient physical memory");
            return false;
        }

	
	    // [Yungho] Allocation
	    if(allocatePhysPages(numPages) == false)
	    	return false;	// failed to allocate memory
	    else
	    */
	    	
	    allocatePhysPages(numPages);
	    lazyload = new Lazyload(coff);

	    return true;
    }

	/**
	 * Release any resources allocated by <tt>loadSections()</tt>.
	 */
    protected void unloadSections() {
    	Lib.debug(dbgPeter, "[+][unloadSections] starting...");
        deallocatePhysPages(pageTable);
        
        return;
    }
    
    
    /**
	 * Handle a user exception. Called by <tt>UserKernel.exceptionHandler()</tt>
	 * . The <i>cause</i> argument identifies which exception occurred; see the
	 * <tt>Processor.exceptionZZZ</tt> constants.
	 * 
	 * @param cause the user exception that occurred.
	 */
	public void handleException(int cause) {
		//Lib.debug(dbgPeter, "[+][handleException] starting...");
		boolean intStatus = Machine.interrupt().disable();
		
		Processor processor = Machine.processor();

		switch (cause) {
		case Processor.exceptionTLBMiss:
			//Lib.debug(dbgPeter, "[+][handleException] exception");
			handleTLB(processor.readRegister(Processor.regBadVAddr), lazyload);
			break;
		default:
			super.handleException(cause);
			break;
		}
		
		Machine.interrupt().restore(intStatus);
	}
	

	private static final int pageSize = Processor.pageSize;

	private static final char dbgProcess = 'a';
	
	private static final char dbgPeter = 'P';
}
